package tree.binarysearchtree;

import tree.TreeNode;

/**
 * @Classname : IncreasingOrderSearchTree
 * @Description :
 * <a href="https://leetcode.cn/problems/increasing-order-search-tree/">897. 递增顺序搜索树</a>
 * @Author : chentianyu
 * @Date 2023/1/26 17:46
 */

// 局部变量记录当前节点
public class IncreasingOrderSearchTree {
    public TreeNode increasingBST(TreeNode root) {
        TreeNode dummy = new TreeNode();
        TreeNode cur = dummy;
        inorder(root, cur);
        return dummy.right;
    }

    private TreeNode inorder(TreeNode root, TreeNode cur) {
        if (root == null) return cur;

        cur = inorder(root.left, cur);
        root.left = null;
        cur.right = root;
        cur = root;
        return inorder(root.right, cur);
    }
}


// 全局变量记录当前节点
class IncreasingOrderSearchTree2 {
    private TreeNode cur;

    public TreeNode increasingBST(TreeNode root) {
        TreeNode dummy = new TreeNode();
        cur = dummy;
        inorder(root);
        return dummy.right;
    }

    private void inorder(TreeNode root) {
        if (root == null) return ;

        inorder(root.left);
        root.left = null;
        cur.right = root;
        cur = root;
        inorder(root.right);
    }
}
